package com.hy;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:二叉树中的最大路径和
 *
 * 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径
 * 至少包含一个 节点，且不一定经过根节点。
 * 路径和 是路径中各节点值的总和。
 * 给你一个二叉树的根节点 root ，返回其 最大路径和 。
 *
 * author: Mr.Du
 * Date: 2023/10/17
 * Time: 17:12
 */
public class MaxPathSum {

    int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs1(root);
        return max;
    }

    /**
     * 最大值的选择就是从当前节点出发，看选择那个孩子，下面left和right分别表示选择左孩子的最大值、选择右孩子的最大值
     * 1、两个孩子都选  root.val + left + right
     * 2、选择左孩子  root.val + left
     * 3、选择右孩子  root.val + right
     * @param root
     * @return 返回条件就是当前节点选左孩子或者右孩子（取它两最大值），因为你只能只一个方向，
     */
    public int dfs(TreeNode root){
        if(root == null) return 0;
        int left = Math.max(0, dfs(root.left));
        int right = Math.max(0, dfs(root.right));
        // case 1
        int cur = left + right + root.val;
        // case 2|3
        int p =  Math.max(left, right) + root.val;
        max = Math.max(max, Math.max(p, cur));
        return p;
    }

    public int dfs1(TreeNode root){
        if(root == null) return 0;
        int left = Math.max(0, dfs(root.left));
        int right = Math.max(0, dfs(root.right));
        max = Math.max(max, left + right + root.val);
        return Math.max(Math.max(left, right) + root.val, 0);
    }
}
